Presolve and statuses CPX_STAT_INForUNBD or IloCplex::InfOrUnbd.

Answer

CPLEX can return a status of infeasible or unbounded because:

• Detection of an unbounded direction does not imply an unbounded objective function. An unbounded objective function requires an unbounded direction and a feasible solution. If CPLEX's presolve detects an unbounded direction before a feasible solution is known, it has proven that the model does not have an optimal solution, regardless of the existence of a feasible solution. So, CPLEX terminates and returns a solution status indicating the model is infeasible or unbounded.

• CPLEX's presolve makes reductions based on the assumption that a bounded, optimal solution exists. This assumption enables it to make additional reductions on models with bounded, optimal solutions, but it loses the ability to distinguish infeasibility and unboundedness during the presolve phase. Users who need to make this distinction can always rerun CPLEX with presolve off after receiving a status indicating the model is infeasible or unbounded.

The following model illustrates how detection of an unbounded direction can occur with an unbounded or infeasible model.

Min -x1 - x2
s.t.
x1 - x2 = 5
x1 - x2 - x3= -5
x1, x2, x3 >= 0

Running this model from CPLEX yields the following presolve message:

Duplicate columns x1 and x2 make problem unbounded.

This message means that presolve has found an unbounded direction, not that it has proven the model has an unbounded objective. The status returned from the optimization indicates the model is infeasible or unbounded. This does not contradict the presolve message. If the model has a feasible solution x* = (x1*, x2*, x3*), then presolve has determined that (t, t, 0) provides an unbounded direction as t increases to infinity. This unbounded direction proves the model is unbounded when combined with x* to give the family of solutions (x1* + t, x2* + t, x3*). Furthermore, turning off presolve reveals that the model is indeed unbounded; consider solutions of the form (5 + t, t, 10). But, presolve has not confirmed that such a feasible solution x* exists, so it cannot conclude the model is unbounded; it can only conclude that it is infeasible or unbounded.

In this previous example, presolve detected an unbounded direction for a model that has an unbounded objective. However, the model could have the unbounded direction without the feasible solution that made the objective unbounded. To see this, take the same model, but fix x3 to 0:

Min -x1 - x2
s.t.
x1 - x2 = 5
x1 - x2 - x3= -5
x3 = 0
x1, x2, x3 >= 0

Running this model within CPLEX results in the same presolve message regarding duplicate columns. After all, nothing has changed regarding columns x1 and x2, so they remain duplicate columns. However, turning off presolve results in an infeasible model; after removing x3 from the model, two identical equality constraints with different right hand sides confirm the infeasibility. So, CPLEX's presolve still found an unbounded direction, but no feasible solution exists. While an unbounded direction exists, the model's objective is not unbounded because no feasible solution exists. This illustrates that detection of an unbounded direction proves that no optimal solution exists for the model, but it does not indicate whether the model has a feasible solution. So, CPLEX can only conclude that the model is infeasible or unbounded.

The following model illustrates how reductions based on the assumption of a bounded optimal solution affect presolve's ability to distinguish infeasibility from unboundedness.

Min 2x1 - 2x2 - 2x3
s.t.
x1 + x2 - 2x3 >= 1
x1 - 2x2 + x3 >= 0
x1, x2, x3 >= 0

A quick look at the model reveals that a feasible solution of (1,0,0) combined with an unbounded direction of (t, t, t) makes the model unbounded as t approaches infinity. However, presolve could come to a different conclusion based on the dual problem:

Max y1
s.t.
y1 + y2 <= 2
y1 - 2y2 <= -2
-2y1 + y2 <= -2
y1, y2 >= 0

Multiplying the first constraint by 2 and adding it to the second and third constraints reveals that y1 and y2 <= 2/3. Looking back at the primal, this means that the reduced cost for x1 is

2 - y1 - y2 >= 2 - 2/3 - 2/3 > 0.

In any bounded, feasible solution, this implies that x1 = 0 in the primal. However, removing x1 from the primal, then adding the two constraints, yields

-x2 - x3 >= 1,

which proves the primal is infeasible. So, presolve could conclude this model is infeasible instead of unbounded. While this behavior may seem odd for infeasible or unbounded models, keep in mind that it can lead to additional reductions and performance improvements for the more common case of a model with an optimal solution.